/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nl.unimaas.games.tron.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;

/**
 *
 * @author Cliff Laschet
 */
public class NGram {

    private static int BOARDSIZE = 13 * 13;
    private Random rnd = new Random();
    private HashMap unigram;
    private HashMap bigram;
    private HashMap trigram;

    /**
     * 
     * @param boardSize 
     */
    public NGram(int boardSize) {
        BOARDSIZE = boardSize;
        this.unigram = new HashMap(BOARDSIZE, 1);
        this.bigram = new HashMap(BOARDSIZE * 3, 1);
        this.trigram = new HashMap(BOARDSIZE * 3 * 3, 1);
    }

    /**
     * 
     */
    public void reset() {
        this.unigram.clear();
        this.bigram.clear();
        this.trigram.clear();
    }

    /**
     * 
     * @param moveList
     * @param reward
     * @param playoutPlayer 
     */
    public void update(int[] moveList, int startingPlayer, int playoutPlayer, double reward, boolean syncMoves) {
        if (syncMoves) {
            updateSyncMoves(moveList, startingPlayer, playoutPlayer, reward);
        } else {
            updateASyncMoves(moveList, startingPlayer, playoutPlayer, reward);
        }
    }

    /**
     * 
     * @param moveList
     * @param startingPlayer
     * @param winner
     * @param reward 
     */
    private void updateASyncMoves(int[] moveList, int startingPlayer, int playoutPlayer, double reward) {
        double curReward = reward;
        String hash;

        if (startingPlayer != playoutPlayer) {
            curReward *= -1;
        }

        for (int i = 0; i < moveList.length; i++) {
            //Unigram part
            hash = getHashKey(0, 0, moveList[i]);
            if (unigram.containsKey(hash)) {
                NGramNode node = (NGramNode) unigram.get(hash);
                node.update(curReward);
            } else {
                unigram.put(hash, new NGramNode(curReward));
            }

            //Bigram part
            if (i > 0) {
                hash = getHashKey(0, moveList[i - 1], moveList[i]);
                if (bigram.containsKey(hash)) {
                    NGramNode node = (NGramNode) bigram.get(hash);
                    node.update(curReward);
                } else {
                    bigram.put(hash, new NGramNode(curReward));
                }

                //Trigram part
                if (i > 1) {
                    hash = getHashKey(moveList[i - 2], moveList[i - 1], moveList[i]);
                    if (trigram.containsKey(hash)) {
                        NGramNode node = (NGramNode) trigram.get(hash);
                        node.update(curReward);
                    } else {
                        trigram.put(hash, new NGramNode(curReward));
                    }
                }
            }

            curReward *= -1;
        }
    }

    /**
     * 
     * @param moveList
     * @param startingPlayer
     * @param winner
     * @param reward 
     */
    private void updateSyncMoves(int[] moveList, int startingPlayer, int playoutPlayer, double reward) {
        double curReward = reward;
        String hash;

        if (startingPlayer != playoutPlayer) {
            curReward *= -1;
        }

        for (int i = 0; i < moveList.length; i++) {
            //Unigram part
            hash = getHashKey(0, 0, moveList[i]);
            if (unigram.containsKey(hash)) {
                NGramNode node = (NGramNode) unigram.get(hash);
                node.update(curReward);
            } else {
                unigram.put(hash, new NGramNode(curReward));
            }
            //Bigram part
            if ((i >= 2)) {
                int lastIndex = i - 1;
                if (i % 2 == 1) {
                    lastIndex = i - 3;
                }
                hash = getHashKey(0, moveList[lastIndex], moveList[i]);
                if (bigram.containsKey(hash)) {
                    NGramNode node = (NGramNode) bigram.get(hash);
                    node.update(curReward);
                } else {
                    bigram.put(hash, new NGramNode(curReward));
                }

                //Trigram part
                if (i >= 4) {
                    int secondIndex = i - 1;
                    int firstIndex = i - 4;
                    if (i % 2 == 1) {
                        secondIndex = i - 3;
                        firstIndex = i - 4;
                    }
                    hash = getHashKey(moveList[firstIndex], moveList[secondIndex], moveList[i]);
                    if (trigram.containsKey(hash)) {
                        NGramNode node = (NGramNode) trigram.get(hash);
                        node.update(curReward);
                    } else {
                        trigram.put(hash, new NGramNode(curReward));
                    }
                }
            }

            curReward *= -1;
        }
    }

    /**
     * 
     * @param history
     * @return 
     */
    public int getUniPosition(ArrayList<Integer> validMoves) {
        double bestValue = -1;
        ArrayList<Integer> bestMoves = new ArrayList<Integer>();
        Iterator<Integer> iterator = validMoves.iterator();
        while (iterator.hasNext()) {
            int curMove = iterator.next();
            String key = getHashKey(0, 0, curMove);
            NGramNode node = (NGramNode) unigram.get(key);
            if (node != null) {
                if (node.getValue() == bestValue) {
                    bestMoves.add(curMove);
                } else if (node.getValue() > bestValue) {
                    bestMoves.clear();
                    bestValue = node.getValue();
                    bestMoves.add(curMove);
                }
            }
        }

        //If we find multiple best moves, choose one random. Otherwise, return the one best move.
        if (bestMoves.isEmpty()) {
            return -1;
        } else if (bestMoves.size() == 1) {
            return bestMoves.get(0);
        } else {
            return bestMoves.get(rnd.nextInt(bestMoves.size()));
        }
    }

    /**
     * 
     * @param moveSequence
     * @param validMoves
     * @return 
     */
    public int getBiPosition(int secondMove, ArrayList<Integer> validMoves) {
        double bestValue = -1;
        ArrayList<Integer> bestMoves = new ArrayList<Integer>();
        Iterator<Integer> iterator = validMoves.iterator();
        while (iterator.hasNext()) {
            int curMove = iterator.next();
            String key = getHashKey(0, secondMove, curMove);
            NGramNode node = (NGramNode) bigram.get(key);
            if (node != null) {
                if (node.getValue() == bestValue) {
                    bestMoves.add(curMove);
                } else if (node.getValue() > bestValue) {
                    bestMoves.clear();
                    bestValue = node.getValue();
                    bestMoves.add(curMove);
                }
            }
        }

        //If we find multiple best moves, choose one random. Otherwise, return the one best move.
        if (bestMoves.isEmpty()) {
            return -1;
        } else if (bestMoves.size() == 1) {
            return bestMoves.get(0);
        } else {
            return bestMoves.get(rnd.nextInt(bestMoves.size()));
        }
    }

    /**
     * 
     * @param firstMove
     * @param secondMove
     * @param validMoves
     * @return 
     */
    public int getTriPosition(int firstMove, int secondMove, ArrayList<Integer> validMoves) {
        double bestValue = -1;
        ArrayList<Integer> bestMoves = new ArrayList<Integer>();
        Iterator<Integer> iterator = validMoves.iterator();
        while (iterator.hasNext()) {
            int curMove = iterator.next();
            String key = getHashKey(firstMove, secondMove, curMove);
            NGramNode node = (NGramNode) trigram.get(key);
            if (node != null) {
                if (node.getValue() == bestValue) {
                    bestMoves.add(curMove);
                } else if (node.getValue() > bestValue) {
                    bestMoves.clear();
                    bestValue = node.getValue();
                    bestMoves.add(curMove);
                }
            }
        }

        //If we find multiple best moves, choose one random. Otherwise, return the one best move.
        if (bestMoves.isEmpty()) {
            return -1;
        } else if (bestMoves.size() == 1) {
            return bestMoves.get(0);
        } else {
            return bestMoves.get(rnd.nextInt(bestMoves.size()));
        }
    }

    /**
     * 
     * @param secondMove
     * @param validMoves
     * @return 
     */
    public int getAvgBiPosition(int secondMove, ArrayList<Integer> validMoves) {
        double[] avgValue = new double[validMoves.size()];
        Iterator<Integer> iterator = validMoves.iterator();
        int j = 0;
        while (iterator.hasNext()) {
            int hitCounter = 0;
            int move = iterator.next();

            String key = getHashKey(0, 0, move);
            NGramNode node = (NGramNode) unigram.get(key);
            double uniValue = 0;
            /*if (node != null) {
            hitCounter++;
            uniValue = node.getValue();
            }*/

            key = getHashKey(0, secondMove, move);
            node = (NGramNode) bigram.get(key);
            double biValue = 0;
            if (node != null) {
                hitCounter++;
                biValue = node.getValue();
            }

            if (hitCounter > 0) {
                avgValue[j] = (uniValue + biValue) / hitCounter;
            } else {
                avgValue[j] = -2; // Dot not consider this move at all when it isnt one of the grams , by setting its value below the -1 treshold
            }
            j++;
        }

        double bestValue = -1;

        //Save the best moves in a list.
        ArrayList<Integer> bestMoves = new ArrayList<Integer>();
        for (int i = 0; i < avgValue.length; i++) {
            if (avgValue[i] == bestValue) {
                bestMoves.add(validMoves.get(i));
            } else if (avgValue[i] > bestValue) {
                bestMoves.clear();
                bestValue = avgValue[i];
                bestMoves.add(validMoves.get(i));
            }
        }

        //If we find multiple best moves, choose one random. Otherwise, return the one best move.
        if (bestMoves.isEmpty()) {
            return -1;
        } else if (bestMoves.size() == 1) {
            return bestMoves.get(0);
        } else {
            return bestMoves.get(rnd.nextInt(bestMoves.size()));
        }
    }

    /**
     * 
     * @param firstMove
     * @param secondMove
     * @param validMoves
     * @return 
     */
    public int getAvgPosition(int firstMove, int secondMove, ArrayList<Integer> validMoves) {
        double[] avgValue = new double[validMoves.size()];
        Iterator<Integer> iterator = validMoves.iterator();
        int j = 0;
        int hitCounter = 0;
        double uniValue, biValue, triValue = 0;
        int move = -1;
        while (iterator.hasNext()) {
            hitCounter = 0;
            move = iterator.next();

            String key = getHashKey(0, 0, move);
            NGramNode node = (NGramNode) unigram.get(key);
            uniValue = 0;
            /*if (node != null) {
            hitCounter++;
            uniValue = node.getValue();
            }*/

            key = getHashKey(0, secondMove, move);
            node = (NGramNode) bigram.get(key);
            biValue = 0;
            if (node != null) {
                hitCounter++;
                biValue = node.getValue();
            }

            key = getHashKey(firstMove, secondMove, move);
            node = (NGramNode) trigram.get(key);
            triValue = 0;
            if (node != null) {
                hitCounter++;
                triValue = node.getValue();
            }

            if (hitCounter > 0) {
                avgValue[j] = (uniValue + biValue + triValue) / hitCounter;
            } else {
                avgValue[j] = -2; // Dot not consider this move at all when it isnt one of the grams , by setting its value below the -1 treshold
            }
            j++;
        }

        double bestValue = -1;

        //Save the best moves in a list.
        ArrayList<Integer> bestMoves = new ArrayList<Integer>();
        for (int i = 0; i < avgValue.length; i++) {
            if (avgValue[i] == bestValue) {
                bestMoves.add(validMoves.get(i));
            } else if (avgValue[i] > bestValue) {
                bestMoves.clear();
                bestValue = avgValue[i];
                bestMoves.add(validMoves.get(i));
            }
        }

        //If we find multiple best moves, choose one random. Otherwise, return the one best move.
        if (bestMoves.isEmpty()) {
            return -1;
        } else if (bestMoves.size() == 1) {
            return bestMoves.get(0);
        } else {
            return bestMoves.get(rnd.nextInt(bestMoves.size()));
        }
    }

    /**
     * 
     * @param firstMove
     * @param secondMove
     * @param thirdMove
     * @return 
     */
    public double getHeuristicValue(int firstMove, int secondMove, int thirdMove) {
        String key = getHashKey(firstMove, secondMove, thirdMove);
        NGramNode node = (NGramNode) bigram.get(key);
        double biValue = 0;
        int hitCounter = 0;
        if (node != null) {
            biValue = node.getValue();
            hitCounter++;
        }
        
        key = getHashKey(firstMove, secondMove, thirdMove);
        node = (NGramNode) bigram.get(key);
        double triValue = 0;
        if (node != null) {
            triValue = node.getValue();
            hitCounter++;
        }
        
        if(hitCounter > 0){
            return ((biValue + triValue) / hitCounter);
        }else{
            return 0;
        }
    }

    /**
     * 
     * @param a
     * @param b
     * @param c
     * @return 
     */
    private static String getHashKey(int a, int b, int c) {
        StringBuilder builder = new StringBuilder(12);
        builder.append(a);
        builder.append(b);
        builder.append(c);
        return builder.toString();
    }
}
